// https://leetcode.cn/problems/subarrays-with-k-different-integers/submissions/558907977/

class Solution {
public:

    int subarraysWithKDistinct(vector<int>& a, int k) {
        unordered_map<int, int> d1, d2;
        int c1 = 0, c2 = 0, ans = 0;
        for (int L1 = 0, L2 = 0, R = 0; R < a.size(); R++) {
            if (++d1[a[R]] == 1) c1++;
            if (++d2[a[R]] == 1) c2++;
            
            //保证第一个窗口一定要有exactly k unique num
            while (L1 < R && c1 > k) {
                if (--d1[a[L1++]] == 0) 
                    c1--;
            }
            
            //保证第二个窗口的 unique num一定要小于k
            while (L2 <= R && c2 >= k) {
                if (--d2[a[L2++]] == 0) 
                    c2--;
            }
            
            //表达式 L2 - L1 表示以当前右指针 R 结束，且具有 K 个不同元素的有效子数组的数量。
            ans += L2 - L1;
        }
        return ans;
    }
};